#ifndef __VEC_H__
#define __VEC_H__

#include <cassert>
#include "memory.h"

// Borrowed from Minisat 1.14, modified for CUDA device.

//=================================================================================================
// 'vec' -- automatically resizable arrays (via 'push()' method):

// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)

template<class T>
class Vec {
public:
	// Constructors:
	__host__ __device__
	Vec ( void ) : _dataPtr(NULL), _size(0), _capacity(0) {}

	__host__ __device__
	Vec ( int size ) : _dataPtr(NULL), _size(0), _capacity(0)
	{ grow_to( size ); }

	__host__ __device__
	Vec ( int size, const T& padding ) : _dataPtr(NULL), _size(0), _capacity(0)
	{ grow_to( size, padding ); }

	// (takes ownership of array -- will be deallocated with 'xfree()')
	__host__ __device__
	Vec ( T* array, int size )
	: _dataPtr(array), _size(size), _capacity(size) {}

	__host__ __device__
	~Vec ( void )
	{ clear( true ); }

	// Ownership of underlying array:
	__host__ __device__
	T* release ( void )
	{
		T* ret = _dataPtr;
		_dataPtr = NULL;
		_size = 0;
		_capacity = 0;
		return ret;
	}
/*
	__host__ __device__
	operator T* (void) { return _dataPtr; }     // (unsafe but convenient)
	__host__ __device__
	operator const T* (void) const { return _dataPtr; }
*/
	__host__ __device__
	T* get_dataPtr( void ) { return _dataPtr; }
	__host__ __device__
	const T* get_dataPtr( void ) const { return _dataPtr; }

	// Size operations:
	__host__ __device__
	bool empty (void) const { return (_size == 0); }
	__host__ __device__
	int size (void) const { return _size; }
	__host__ __device__
	int capacity (void) const { return _capacity; }

	__host__ __device__
	void shrink ( int nElems )
	{
#ifdef __CUDA_ARCH__
		if ( nElems > _size )
		{ printf("[Vec] ERROR: shrink size = %d > _size = %d\n", nElems, _size ); }
#else
		assert( nElems <= _size );
#endif
		for ( int i = 0; i < nElems; ++i )
		{
			--_size;
			_dataPtr[_size].~T();
		}
	}

	__host__ __device__
	void pop_back ( void ) { --_size; _dataPtr[_size].~T(); }
	__host__ __device__
	void grow_to ( int size );
	__host__ __device__
	void grow_to ( int size, const T& padding );
	__host__ __device__
	void clear ( bool dealloc = false );
	__host__ __device__
	void reserve ( int size ) { grow( size ); }

	// Stack interface:

	__host__ __device__
	void push_back (void)
	{
		if ( _size == _capacity )
		{ grow( _size + 1 ); }
		
		new (&_dataPtr[_size]) T();
		++_size;
	}

	__host__ __device__
	void push_back ( const T& elem )
	{
		if ( _size == _capacity )
		{ grow( _size + 1 ); }
		new (&_dataPtr[_size]) T(elem);
		++_size;
	}

	__host__ __device__
	const T& front (void) const
	{
		if ( _size == 0 )
		{ printf( "[Vec] ERROR: front() is called while _size == 0\n" ); }
		return _dataPtr[0];
	}
	__host__ __device__
	T& front (void)
	{
		if ( _size == 0 )
		{ printf( "[Vec] ERROR: front() is called while _size == 0\n" ); }
		return _dataPtr[0];
	}
	__host__ __device__
	const T& back (void) const
	{
		if ( _size == 0 )
		{
			printf( "[Vec] ERROR: back() is called while _size == 0\n" );
			return _dataPtr[0];
		}
		else
		{ return _dataPtr[_size-1]; }
	}
	__host__ __device__
	T& back (void)
	{
		if ( _size == 0 )
		{
			printf( "[Vec] ERROR: back() is called while _size == 0\n" );
			return _dataPtr[0];
		}
		else
		{ return _dataPtr[_size-1]; }
	}

	// Vector interface:
	__host__ __device__
	const T& at ( int index ) const
	{
		if ( index >= _size )
		{ printf( "[Vec] ERROR: at() index = %d out > size = %d.\n", index, _size ); }
		return _dataPtr[index];
	}
	__host__ __device__
	T& at ( int index )
	{
		if ( index >= _size )
		{ printf( "[Vec] ERROR: at() index = %d out > size = %d.\n", index, _size ); }
		return _dataPtr[index];
	}
	__host__ __device__
	const T& operator [] ( int index ) const { return _dataPtr[index]; }
	__host__ __device__
	T& operator [] ( int index ) { return _dataPtr[index]; }

	// Don't allow copying (error prone):
	__host__ __device__
	Vec<T>& operator = (Vec<T>& other)
	{
		printf( "[Vec] Copy (operator =) is not allowed. return NULL.\n" );
		return NULL;
	}

	__host__ __device__
	Vec (Vec<T>& other)
	{ printf( "[Vec] Copy consturctor is not allowed.\n" ); }

	// Duplicatation (preferred instead):
	__host__ __device__
	void copy_to( Vec<T>& copy ) const
	{
		copy.clear();
		copy.grow_to( _size );

		for ( int i = 0; i < _size; ++i )
		{ new (&copy[i]) T(_dataPtr[i]); }
	}

	__host__ __device__
	void move_to( Vec<T>& dest )
	{
		dest.clear( true );
		dest._dataPtr = _dataPtr;
		dest._size = _size;
		dest._capacity = _capacity;
		_dataPtr = NULL;
		_size = 0;
		_capacity = 0;
	}

	__host__ __device__
	void erase( int index )
	{
		if ( (index >= _size) || (index < 0) )
		{ printf("[Vec] erase(): illegal index %d\n", index); return; }

		--_size;
		for ( int i = index; i < _size; ++i )
		{ new (&_dataPtr[i]) T(_dataPtr[i+1]); }
	}

	__host__ __device__
	void fast_erase( int index )
	{
		_dataPtr[index] = _dataPtr[_size-1];
		--_size;
	}

private:
	T*  _dataPtr;
	int _size;
	int _capacity;

	__host__ __device__
	void grow( int min_cap );
};

template<class T>
__host__ __device__ inline
void Vec<T>::grow( int min_cap )
{
	if (min_cap <= _capacity)
	{ return; }

#ifdef __CUDA_ARCH__
	int oldCapacity = _capacity;
#endif
	if (_capacity == 0)
	{ _capacity = (min_cap >= 2) ? min_cap : 2; }
	else
	{
		do { _capacity = ((_capacity*3)+1) >> 1; }
		while (_capacity < min_cap);
	}

#ifdef __CUDA_ARCH__
	_dataPtr = xrealloc( _dataPtr, (sizeof(T) * oldCapacity), (sizeof(T) * _capacity) );
#else
	_dataPtr = xrealloc( _dataPtr, (sizeof(T) * _capacity) );
#endif
	return;
}

template<class T>
__host__ __device__ inline
void Vec<T>::grow_to( int size, const T& padding )
{
	if ( _size >= size )
	{ return; }

	grow( size );

	for ( int i = _size; i < size; ++i )
	{ new (&_dataPtr[i]) T(padding); }

	_size = size;
	return;
}

template<class T>
__host__ __device__ inline
void Vec<T>::grow_to( int size )
{
	if ( _size >= size )
	{ return; }

	grow( size );

	for ( int i = _size; i < size; ++i )
	{ new (&_dataPtr[i]) T(); }

	_size = size;
}

template<class T>
__host__ __device__ inline
void Vec<T>::clear( bool dealloc ) {
    if ( _dataPtr != NULL )
	{
        for ( int i = 0; i < _size; ++i )
		{ _dataPtr[i].~T(); }

        _size = 0;

        if ( dealloc == true )
		{
			xfree(_dataPtr);
			_dataPtr = NULL;
			_capacity = 0;
		}
	}
}

#endif /* __VEC_H__ */
